package com.isaiah.graph;

import com.isaiah.list.ArrayList;

import java.util.Arrays;

/**
 * @Title: 基于邻接矩阵的表向图的表示
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/319:15
 */
public class Graph {
    /** 存储顶点的集合 */
    private ArrayList<String> vertexList;
    /** 存储图对应的边 */
    private int[][] edges;
    /** 表示边的数目 */
    private int numOfEdges;

    /**
     * 记录节点是否被访问过
     */
    private boolean[] isVisited;

    public Graph(int n) {
        // 初始化矩阵
        this.edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.addLast(vertex);
    }

    /**
     * 添加边
     * @param v1 表示顶点下标，即第几个顶点： "A"->"B"  "A":0  "B":1
     * @param v2 第二个顶点对应的下标
     * @param weight 权重
     */
    public void insertEdge(int v1, int v2, int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges ++;
    }

    /**
     * 返回顶点个数
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.getSize();
    }

    /**
     * 返回边的数目
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

    /**
     * 返回结点索引对应的数据， 如0:"A" 1:"B" 2:"C"
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    /**
     * 返回某条边的权重
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2){
        return edges[v1][v2];
    }

    /**
     * 打印图对应的矩阵
     * @return
     */

    public void  showGraph() {
        for (int[] link : edges){
            System.err.println(Arrays.toString(link));
        }
    }

    /**
     * 获取第一个邻接点的下标w
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index){
        for (int j = 0; j < vertexList.getSize(); j++){
            if (edges[index][j] > 0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接点的下标获取下一个邻接点
     * @return
     */
    public int getNextNeighbor(int v1, int v2){
        for (int j = v2+1; j < vertexList.getSize(); j++){
            if (edges[v1][v2] > 0){
                return j;
            }
        }
        return -1;
    }


    /**
     * 深度优先遍历
     */
    public void dfs(){
        // 遍历所有结点，进行dfs[回溯]
        for(int i = 0; i < getNumOfVertex(); i++){
            if (!isVisited[i]){
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     * @param isVisited
     * @param i 第一次就是0
     */
    private void dfs(boolean[] isVisited, int i) {
        // 首先我们访问该结点
        System.out.print(getValueByIndex(i) + "->");
        // 将该结点标记为已访问
        isVisited[i] = true;
        // 查找结点i的第一个邻接点w
        int w = getFirstNeighbor(i);
        while (w != -1){    // 说明有
            if (!isVisited[w]){
                dfs(isVisited, w);
            }
            // 如果w结点已经被访问过
            w = getNextNeighbor(i, w);
        }
    }
}
